package com.yxyu.sort.impl;

import com.yxyu.sort.SortBase;

/**
 * 快速排序
 * 快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
 * @author yl
 */
public class QuickSort implements SortBase {

    @Override
    public String getName() {
        return "快速排序";
    }

    @Override
    public int[] sort(int[] numbers) {
        return sort(numbers, 0, numbers.length - 1);
    }

    /**
     *
     * @param ns
     * @param b 开始点
     * @param e 结束点
     * @return
     */
    private int[] sort(int[] ns, int b, int e) {
        if (b >= e) {
            // 出口
            return ns;
        }

        // 选择基准数
        int p = ns[b];
        int begin = b;
        int end = e;

        while (begin < end) {
            while ((begin < end) && p > ns[begin]) {
                // 右侧指针跳
                begin++;
            }
            while ((begin < end) && p < ns[end]) {
                //　左侧指针跳
                end--;
            }
            if (ns[begin] == ns[end] && (begin < end) ) {
                begin++;
            } else if (begin != end){
                // 左右指针都跳不动了
                // 交换两个阻碍点
                int temp = ns[begin];
                ns[begin] = ns[end];
                ns[end] = temp;
            }
        }

        sort(ns, b, begin - 1);
        sort(ns, end + 1, e);
        return ns;
    }
}
